#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution
{
public:
    long long totalCost(vector<int> &costs, int k, int candidates)
    {
        long long total = 0;
        int headIndex = 0;
        int endIndex = 0;
        priority_queue<int, vector<int>, greater<int>> head;
        priority_queue<int, vector<int>, greater<int>> end;

        if (candidates * 2 > costs.size())
        {
            headIndex = costs.size() - 1;
            endIndex = costs.size() - 1;
            for (int i = 0; i < costs.size(); i++)
            {
                head.push(costs[i]);
            }
        }
        else
        {
            headIndex = candidates;
            endIndex = costs.size() - 1 - candidates; // 4=9-1-4
            for (int i = 0; i < headIndex; i++)
            {
                head.push(costs[i]);
                cout << "head: " << costs[i] << endl;
            }
            for (int i = endIndex + 1; i < costs.size(); i++)
            {
                end.push(costs[i]);
                cout << "end: " << costs[i] << endl;
            }
        }

        for (size_t i = 0; i < k; i++)
        {
            if (head.empty())
            {
                // end is not empty
                total += end.top();
                end.pop();
            }
            else if (end.empty())
            {
                // head is not empty
                total += head.top();
                head.pop();
            }
            else
            {
                // both are not empty
                cout << "head: " << head.top() << " end: " << end.top() << endl;
                if (head.top() <= end.top())
                {
                    cout << "head is smaller" << endl;
                    total += head.top();
                    head.pop();
                    if (headIndex <= endIndex)
                    {
                        cout << "headIndex: " << headIndex << ',' << "endIndex: " << endIndex << ',' << "add:" << costs[headIndex] << endl;
                        head.push(costs[headIndex]);
                        headIndex++;
                    }
                }
                else
                {
                    cout << "end is smaller" << endl;
                    total += end.top();
                    end.pop();
                    if (headIndex <= endIndex)
                    {
                        cout << "headIndex: " << headIndex << ',' << "endIndex: " << endIndex << ',' << "add:" << costs[endIndex] << endl;
                        end.push(costs[endIndex]);
                        endIndex--;
                    }
                }
            }
        }
        return total;
    }
};

int main()
{
    cout << "Code2462" << endl;
    Solution s;
    // std::vector<int> costs = {17, 12, 10, 2, 7, 2, 11, 20, 8};
    std::vector<int> costs = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    int k = 3, candidates = 4;
    cout << "Total cost: " << s.totalCost(costs, k, candidates) << endl;
    return 0;
}
// 17 12 10 2 - 2 7 2 11